Transactions on Combinatorics
Volume:12 Issue: 2, Jun 2023

In this paper, we introduce an approximation for the $k$-nearest neighbor graph ($k$-NNG) on a point set $P$ in $\mathbb{R}^d$. For any given $\varepsilon>0$, we construct a graph, that we call the \emph{approximate $k$-NNG}, where the edge with the $i$th smallest length incident to a point $p$ in this graph is within a factor of $(1+\varepsilon)$ of the length of the edge with the $i$th smallest length incident to $p$ in the $k$-NNG. For a set $P$ of $n$ moving points in $\mathbb{R}^d$, where the trajectory of each point $p\in P$ is given by $d$ polynomial functions of constant bounded degree, where each function gives one of the $d$ coordinates of $p$, we compute the number of combinatorial changes to the approximate $k$-NNG, and provide a kinetic data structure (KDS) for maintenance of the edges of the approximate $k$-NNG over time. Our KDS processes $O(kn^2\log^{d+1} n)$ events, each in time $O(\log^{d+1}n)$.

Let $G$ be a connected graph and $W=\{w_1, w_2,\ldots,w_k\}$ be an ordered subset of vertices of $G$. For any vertex $v$ of $G$, the ordered $k$-vector $$r(v|W)=(d(v,w_1), d(v,w_2),\ldots,d(v,w_k))$$ is called the metric representation of $v$ with respect to $W$, where $d(x,y)$ is the distance between the vertices $x$ and $y$. A set $W$ is called a resolving set for $G$ if distinct vertices of $G$ have distinct metric representations with respect to $W$. The minimum cardinality of a resolving set for $G$ is its metric dimension denoted by $\dim(G)$. A resolving set $W$ is called a non-isolated resolving set for $G$ if the induced subgraph $\langle W\rangle$ of $G$ has no isolated vertices. The minimum cardinality of a non-isolated resolving set for $G$ is called the non-isolated resolving number of $G$ and denoted by $nr(G)$. The aim of this paper is to find properties of unicyclic graphs that have non-isolated resolving number $2$ and then to characterize all these graphs.

In this paper, we study the domination number of middle graphs. Indeed, we obtain tight bounds for this number in terms of the order of the graph G. We also compute the domination number of some families of graphs such as star graphs, double start graphs, path graphs, cycle graphs, wheel graphs, complete graphs, complete bipartite graphs and friendship graphs, explicitly. Moreover, some Nordhaus-Gaddum-like relations are presented for the domination number of middle graphs.

The main goal of this paper is to study the modified $F$-indices (modified first Zagreb index and modified forgotten topological index) of random $m$-oriented recursive trees (RMORTs). First, through two recurrence equations, we compute the mean and the variance of these indices in our random tree model. Second, we show four convergence in probability based on these indices. Third, the asymptotic normalities, through the martingale central limit theorem, are given.

A graph $G$ is called semi square stable if $\alpha (G^{2})=i(G)$ where $%\alpha (G^{2})$ is the independence number of $G^{2}$ and $i(G)$ is the independent dominating number of $G$. A subset $S$ of the vertex set of a graph $G$ is an efficient dominating set if $S$ is an independent set and every vertex of $G$ is either in $S$ or adjacent to exactly one vertex of $%S. $In this paper, we show that every square stable graph has an efficient dominating set and if a graph has an efficient dominating set, then it is semi square stable. We characterize when the join and the corona product of two disjoint graphs are semi square sable graphs and when they have efficient dominating sets.